package graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class orangesRotting {
    // int count = 0;
    // int time = 0;
    // // ArrayList<int[]> list = new ArrayList<>();
    // Deque<int[]> queue = new ArrayDeque<>();

    // public int orangesRotting(int[][] grid) {
    // // 统计腐烂橘子的位置，以及新鲜橘子的个数
    // int x = grid.length, y = grid[0].length;

    // boolean[][] mark = new boolean[x][y];

    // for (int i = 0; i < x; i++) {
    // for (int j = 0; j < y; j++) {
    // if (grid[i][j] == 1) {
    // count++;
    // } else if (grid[i][j] == 2) {
    // queue.offer(new int[] { i, j });
    // mark[i][j] = true;

    // }
    // }
    // }
    // if (count == 0) {
    // return 0;
    // }
    // // 维护一个flag，表明每分钟内是否有新橘子变坏，没有则表明无法腐烂
    // while (true) {
    // // boolean flag = false;

    // // flag = flag || bfs(mark, grid);

    // // if (!flag) {
    // // break;
    // // } else {
    // // time++;
    // // }
    // boolean flag = false;
    // ArrayList<int[]> direction = new ArrayList<>(4);
    // // 上下左右
    // direction.add(new int[] { 0, -1 });
    // direction.add(new int[] { 0, 1 });
    // direction.add(new int[] { -1, 0 });
    // direction.add(new int[] { 1, 0 });

    // boolean subFlag = false;
    // // 每一层的元素个数
    // int nums = queue.size();
    // if (nums == 0) {
    // break;
    // }
    // for (int i = 0; i < nums; i++) {
    // int[] poll = queue.poll();
    // x = poll[0];
    // y = poll[1];
    // for (int[] item : direction) {
    // if (x + item[0] < 0 || x + item[0] >= mark.length || y + item[1] < 0
    // || y + item[1] >= mark[0].length) {
    // // 越界
    // continue;
    // } else {
    // if (!mark[x + item[0]][y + item[1]] && grid[x + item[0]][y + item[1]] == 1) {
    // mark[x + item[0]][y + item[1]] = true;
    // grid[x + item[0]][y + item[1]] = 2;
    // queue.offer(new int[] { x + item[0], y + item[1] });
    // subFlag = true;
    // count--;

    // }
    // }
    // }
    // flag = flag || subFlag;
    // }
    // if (!flag) {
    // break;
    // }
    // time++;

    // }

    // return count > 0 ? -1 : time;
    // }

    // public boolean bfs(boolean[][] mark, int[][] grid) {
    // boolean flag = false;
    // ArrayList<int[]> direction = new ArrayList<>(4);
    // // 上下左右
    // direction.add(new int[] { 0, -1 });
    // direction.add(new int[] { 0, 1 });
    // direction.add(new int[] { -1, 0 });
    // direction.add(new int[] { 1, 0 });

    // boolean subFlag = false;
    // // 每一层的元素个数
    // int nums = queue.size();
    // if (nums == 0) {
    // return false;
    // }
    // for (int i = 0; i < nums; i++) {
    // int[] poll = queue.poll();
    // int x = poll[0], y = poll[1];
    // for (int[] item : direction) {
    // if (x + item[0] < 0 || x + item[0] >= mark.length || y + item[1] < 0
    // || y + item[1] >= mark[0].length) {
    // // 越界
    // continue;
    // } else {
    // if (!mark[x + item[0]][y + item[1]] && grid[x + item[0]][y + item[1]] == 1) {
    // mark[x + item[0]][y + item[1]] = true;
    // grid[x + item[0]][y + item[1]] = 2;
    // queue.offer(new int[] { x + item[0], y + item[1] });
    // subFlag = true;
    // count--;

    // }
    // }
    // }
    // flag = flag || subFlag;
    // }

    // return flag;
    // }
    int[] dirX = new int[] { -1, 0, 1, 0 };
    int[] dirY = new int[] { 0, 1, 0, -1 };

    public int orangesRotting(int[][] grid) {
        int count = 0, rot = 0, time = 0;
        Deque<int[]> queue = new ArrayDeque();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    count++;
                } else if (grid[i][j] == 2) {
                    queue.offer(new int[] { i, j });
                    rot++;
                }
            }
        }
        if (rot > 0 && count == 0) {
            return 0;
        } else if (rot == 0 && count > 0) {
            return -1;
        }
        while (true) {
            boolean flag = false;
            // 层序遍历
            int num = queue.size();

            if (num == 0) {
                break;
            }

            for (int i = 0; i < num; i++) {
                int[] item = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int x = item[0] + dirX[0];
                    int y = item[1] + dirY[0];
                    if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) {

                        continue;
                    } else {

                        if (grid[x][y] == 1) {
                            grid[x][y] = 2;
                            queue.offer(new int[] { x, y });
                            flag = flag || true;
                            count--;
                        }
                    }

                }
            }
            if (!flag) {
                break;
            }
            time++;
        }
        return count > 0 ? -1 : time;

    }

    public static void main(String[] args) {
        // int[][] grid = new int[][] {
        // { 2, 1, 1 },
        // { 1, 1, 1 },
        // { 0, 1, 2 }
        // };
        // int[][] grid = new int[][] {
        // { 2, 1, 1 },
        // { 1, 0, 0 },
        // { 0, 1, 1 }
        // };
        int[][] grid = new int[][] {
                { 2, 1, 1 },
                { 1, 1, 0 },
                { 0, 1, 1 }
        };
        // int[][] grid = new int[][] {
        // { 2, 1, 1 },
        // { 0, 1, 1 },
        // { 1, 0, 1 }
        // };
        // int[][] grid = new int[][] {
        // { 0, 2}
        // };
        orangesRotting item = new orangesRotting();
        System.out.println(item.orangesRotting(grid));
    }
}
